package arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目：合并数组区间
 * y:
 *  1 8
 *  2 4
 *  9 10
 *  10 16
 *  合并后： 1 8
 *           9 16
 * @Author Gavin
 * @date 2022.01.03 15:00
 */
public class array_13 {
    /**
     * 解题思路：
     * 首先按照各个区间的start开始排序
     * 然后取出最后一个间进行比较start和end
     * 如果第一个的end大于第二个的start，小于第二个的end，那么就更新第一个的
     * end为第二个的end
     */
    public class Interval{
        int start;
        int end;
        Interval(){start=0;end=0;}
        Interval(int s,int e){start=s;end=e;}
    }
    //Time:O(n*log(n)) Space:O(1)
    public List<Interval> merge(List<Interval> intervals){
        List<Interval> result=new ArrayList<>();
        //首先对list里面的元素按照start进行排序
        //这一步是关节点，主要就是排序
        intervals.sort((a,b)->a.start-b.start);
        for(Interval pre:intervals){
            int n=result.size();
            if(result.isEmpty()||result.get(n-1).end<pre.start){
                result.add(pre);
            }else{
                result.get(n-1).end=Math.max(result.get(n-1).end,pre.end);
            }
        }
        return result;
    }
}
